package com.yun.algorithmproblem.leetcode;

public class Leetcode2140 {

	public static void main(String[] args) {
		Leetcode2140 obj = new Leetcode2140();
		//[12,46],[78,19],[63,15],[79,62],[13,10];
		//int[][] questions=new int[][]{{12,46},{78,19},{63,15},{79,62},{13,10}};
		int[][] questions = new int[][] {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
		System.out.println(obj.mostPoints(questions));
	}

	public long mostPoints(int[][] questions) {
		long max = 0;
		long[] leftMax = new long[questions.length];
		for (int i = 0; i < questions.length; i++) {
			if (i != 0) {
				leftMax[i] = Math.max(leftMax[i - 1], leftMax[i]);
			}
			long currentNum = leftMax[i] + questions[i][0];
			max = Math.max(max, currentNum);
			long next = i + 1 + questions[i][1];
			if (next < questions.length) {
				leftMax[(int) next] = Math.max(leftMax[(int) next],currentNum);
			}
		}
		return max;
	}
}
